/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-palindromic-subsequence
   @Language: C++
   @Datetime: 19-06-14 16:41
   */

// Method DP, Time O(n^2), Space O(n^2), 50ms
class Solution {
public:
	/**
	 * @param s: the maximum length of s is 1000
	 * @return: the longest palindromic subsequence's length
	 */
	int longestPalindromeSubseq(string &s) {
		// write your code here
		int n=s.length();
		if(n<2) return n;
		vector<vector<int> > dp(n,vector<int>(n,0));
		for(int i=n; i--;){
			dp[i][i]=1;
			for(int j=i+1; j<n; ++j){
				if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
				else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
			}
		}
		return dp[0][n-1];
	}
};

// Method DP, Time O(n^2), Space O(n), time 50ms
class Solution {
public:
	/**
	 * @param s: the maximum length of s is 1000
	 * @return: the longest palindromic subsequence's length
	 */
	int longestPalindromeSubseq(string &s) {
		// write your code here
		int n=s.length(), res=0;
		if(n<2) return n;
		vector<int> dp(n,1);
		for(int i=n; i--;){
			for(int j=i+1, len=0, t=0; j<n; ++j){
				t=dp[j];
				if(s[i]==s[j]) dp[j]=len+2;
				len=max(len,t);
				res=max(res,dp[j]);
			}
		}
		return res;
	}
};

// Method memorized search, Time O(n^2), Space O(n^2), Time 50ms
class Solution {
	int core(string &s, int i, int j, vector<vector<int> > &mem){
		if(i>j) return 0;
		if(i==j) return 1;
		if(mem[i][j]) return mem[i][j];
		if(s[i]==s[j]) return mem[i][j]=core(s,i+1,j-1,mem)+2;
		else return mem[i][j]=max(core(s,i+1,j,mem),core(s,i,j-1,mem));
	}
public:
	/**
	 * @param s: the maximum length of s is 1000
	 * @return: the longest palindromic subsequence's length
	 */
	int longestPalindromeSubseq(string &s) {
		// write your code here
		int n=s.length();
		vector<vector<int> > mem(n,vector<int>(n,0));
		return core(s,0,n-1,mem);
	}
};
